package com.orcwar.util;

import java.util.ArrayList;
import java.util.List;

import com.orcwar.engine.OWTile;

public class Algorithm {

	public static List<ComposanteConnexe> countNbComposantesConnexes(
			List<List<OWTile>> map) {
		List<ComposanteConnexe> comps = new ArrayList<ComposanteConnexe>();
		int tag = 1;
		// init the matrix that contains the tags
		int[][] tags = new int[map.size()][map.get(0).size()];

		// algo
		for (int row = 0; row < map.size(); row++) {
			for (int col = 0; col < map.get(row).size(); col++) {
				// for each tile
				OWTile tile = map.get(row).get(col);
				if (tile.canGoThrough()) {
					// only tagging passable tiles
					// Get neighbours' tag. Only top and left have one
					int upTag = row > 0 ? tags[row - 1][col] : 0;
					int leftTag = col > 0 ? tags[row][col - 1] : 0;
					if (upTag != 0 && leftTag != 0) {
						// 2 tags
						if (upTag != leftTag) {
							// different, fuse the 2 groups and use up
							fuse(upTag, leftTag, comps);
							tags[row][col] = upTag;
						} else {
							// same, use up
							tags[row][col] = upTag;
						}
					} else if (upTag == 0 && leftTag != 0) {
						// only left, use it
						tags[row][col] = leftTag;
					} else if (upTag != 0 && leftTag == 0) {
						// only up, use it
						tags[row][col] = upTag;
					} else {
						// new group!
						comps.add(new ComposanteConnexe(tag));
						tags[row][col] = tag;
						tag++;
					}

				}

			}
		}

		// store tags fused
		for (int row = 0; row < map.size(); row++) {
			for (int col = 0; col < map.get(row).size(); col++) {
				int tagNotFused = tags[row][col];
				for (int i = 0; i < comps.size(); i++) {
					if (comps.get(i).contains(tagNotFused)) {
						map.get(row).get(col).setTag(i);
					}
				}
			}
		}

		return comps;
	}

	private static void fuse(int upTag, int leftTag,
			List<ComposanteConnexe> comps) {
		// always delete left and add all in up
		// first search the leftTag group
		// search for a group with only leftTag and not upTag, as that would
		// mean they are already fused
		ComposanteConnexe compToRemove = null;
		for (ComposanteConnexe c : comps) {
			if (c.contains(leftTag) && !c.contains(upTag)) {
				compToRemove = c;
			}
		}
		// Now if it is not null (not yet fused) fuse!
		if (compToRemove != null) {
			comps.remove(compToRemove);
			for (ComposanteConnexe c : comps) {
				if (c.contains(upTag)) {
					c.getTags().addAll(compToRemove.getTags());
				}
			}
		}

	}

}
